Be aware of common issues: forgetting visited checks, incorrect initialization, and how BFS behaves on disconnected graphs.
- A key mistake is forgetting to use a `visited` set. This can cause the algorithm to revisit nodes and get stuck in an infinite loop in graphs with cycles.
- Incorrectly initializing `level` or `parent` maps can lead to wrong path lengths and reconstructions. Always set initial levels to infinity and the source's level to 0.
- On disconnected graphs, a single BFS run from a source `s` will only visit nodes in the same connected component as `s`.
- To traverse all nodes in a disconnected graph, you must loop through every vertex and start a new BFS if the vertex hasn't been visited yet.
Common BFS Pitfalls
| Pitfall | Symptom | Fix |
|---|---|---|
No visited check |
Infinite loop on cycles, duplicate visits | Use a set and add nodes on first discovery |
| Wrong initialization | Incorrect levels or paths | Initialize levels to ∞, source level to 0 |
| Disconnected graph | Missed vertices | Use an outer loop over all vertices |